#pragma once

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <string>
#include <memory.h>

using namespace std;

namespace qds
{
    template<class T>
    class vector
    {
        public:
        typedef T value_type;
        typedef value_type* iterator;
        typedef const value_type* const_iterator;

        //默认构造
        vector()
            :_start(nullptr)
             ,_finish(nullptr)
             ,_end_of_storage(nullptr)
        {}

        //迭代器进行构造
        //一个类模板的成员函数,又可以是一个函数模板
        template<class InputIterator>
        vector(InputIterator first, InputIterator last)
            :_start(nullptr)
             ,_finish(nullptr)
             ,_end_of_storage(nullptr)
        {
           while(first != last)
           {
               push_back(*first);
               ++first;
           }
        }

        //根据STL的分类,iteraor包括:
        //input_iterator:只能单步向前迭代元素,不允许修改由该类迭代器引用的元素
        //output_iterator:只能单步向前迭代元素
        //不同的是该类迭代器对元素只有写的权力
        //forward_iterator:可以在一个正确的区间进行读写操作
        //它拥有input_iterator的所有特性,和output_iterator的部分特性
        //以及单步向前迭代元素的能力
        //bidirectional_iterator:在forward_iterator的基础上提供了单步向后迭代元素的能力
        //randomaccess_iterator:可以完成上面所有迭代器的工作
        //它自己独有的特性就是可以像指针那样进行算数计算
        //而不仅仅只有单步向前或者向后迭代

        //传统写法
        //拷贝构造
        vector(const vector<T>& v)
        {
            _start = new T[v.capacity()];
            _finish = _start + v.size();
            _end_of_storage = _start + v.capacity();

            //错误写法
            //memcpy(_start, v._start, sizeof(T) * v.size());
        
            //正确写法
            for(size_t i = 0; i < size(); ++i)
            {
                _start[i] = v._start[i];
            }
        }

        //swap(v1, v2); 会进行三个深拷贝
        //v1.swap(v2); 只会交换成员变量的指针
        void swap(vector<T>& v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_end_of_storage, v._end_of_storage);
        }

        //现代写法
        //vector(const vector& v)
        //vector(const vector<T>& v)//推荐这样写
        //    :_start(nullptr)
        //     ,_finish(nullptr)
        //     ,_end_of_storage(nullptr)
        //{
        //    //利用构造函数构造一个新的对象,让后将这个新的对象与自己进行交换
        //    
        //    vector<T> tmp(v.begin(), v.end());
        //    swap(tmp);
        //}

        ~vector()
        {
            if (_start)
            {
                delete[] _start;
                _start = _finish = _end_of_storage = nullptr;
            }
        }

        const_iterator begin() const
        {
            return _start;
        }

        iterator begin()
        {
            return _start;
        }

        const_iterator end() const
        {
            return _finish;
        }

        iterator end()
        {
            return _finish;
        }

        size_t size() const 
        {
            return _finish - _start;
        }

        size_t capacity() const 
        {
            return _end_of_storage - _start;
        }

        const T& operator[](size_t i) const 
        {
            assert(i < size());
            return _start[i];
        }

        T& operator[](size_t i)
        {
            assert(i < size());
            return _start[i];
        }

        //赋值重载
        //传统写法
        //vector<T>& operator=(const vector<T>& v)
        //{
        //    if(this != &v)
        //    {
        //        iterator tmp = new T[v.capacity()];
        //        memcpy(tmp, _start, sizeof(T) * size());
        //        delete[] _start;
        //        _start = tmp;
        //        _finish = _start + v.end();
        //        _end_of_storage = _start + v.capacity();

        //    }
        //    return *this;
        //}

        //赋值重载
        //现代写法
        //这里利用拷贝构造,拷贝构造出一个对象,利用swap进行交换
        //出了作用域,原来的vector因为进行过交换,会自动调用析构函数,销毁原来的对象
        vector<T>& operator=(vector<T> v)
        {
            swap(v);
            return *this;
        }

        void reserve(size_t n)
        {
            if (n > capacity())
            {
                T* tmp = new T[n];
                //提前保存size()的值,用来下面计算_finish
                size_t sz = size();

                //如果原来的_start是空的话,直接指向新的空间就行了
                
                //错误写法
                //if (_start)
                //{
                //    memcpy(tmp, _start, sizeof(T) * size());
                //    delete[] _start;
                //}
                
                //正确写法
                if(_start)
                {
                    for (size_t i = 0; i < sz; ++i)
                    {
                        //T是int,一个一个拷贝没问题
                        //T是string,一个一个拷贝调用的是T的深拷贝赋值,也没问题
                        tmp[i] = _start[i];
                    }
                    delete[] _start;
                }

                _start = tmp;
                //注意这里的size()中的_start已经被更新过了
                //所以这里的size会得到一个错误的值
                //size()的值,需要提前保存
                _finish = _start + sz;
                _end_of_storage = _start + n;
            }
        }

        //这里需要分三种情况来进行讨论
        //n < size()
        //size() < n < capacity()
        //n > capacity()
        //这里采用匿名函数构建的参数,不用担心它的生命周期只存在于当前的这一行
        //这是c++的特殊规矩,const修饰的引用对象,如果是匿名对象进行复制
        //那么匿名对象的生命周期会延长,直到这个函数结束
        void resize(size_t n, const T& value = T())
        {
            if (n < size())
            {
                _finish = _start + n;
            }
            else 
            {
                if (n > capacity())
                {
                    reserve(n);
                }

                while(_start + n != _finish)
                {
                    *_finish = value;
                    ++_finish;
                }
            }
        }

        void push_back(const T& x)
        {
            if (_end_of_storage == _finish)
            {
                reserve(capacity() == 0 ? 1 : capacity() * 2);
            }
            *_finish = x;
            ++_finish;
        }

        void pop_back()
        {
            assert(_finish > _start);
            --_finish;
        }

        iterator insert(iterator pos, const T& x)
        {
            //头插
            assert(pos >= _start);
            //尾插
            assert(pos <= _finish);

            if(_end_of_storage == _finish)
            {
                //如果进行扩容,就会导致pos失效,reserve()会开辟新的空间,所以需要提前记录pos的位置
                size_t len = pos - _start;
                reserve(capacity() == 0 ? 1 : capacity() * 2);
                pos = _start + len;
            }
            iterator end = _finish - 1;
            while(end >= pos)
            {
                *(end + 1) = *end;
                --end;
            }
           *pos = x;
           ++_finish;
           return pos;
        }

        iterator erase(iterator pos)
        {
            assert(pos >= _start);
            //最后一个元素位置的下一个位置,可以进行插入,但是不能进行删除
            assert(pos < _finish);

            iterator begin = pos;
            while(begin < _finish - 1)
            {
                *begin = *(begin + 1);
                ++begin;
            }
            --_finish;
            return pos;
        }

        private:
        iterator _start;
        iterator _finish;
        iterator _end_of_storage;
    };
}
